/* IntArraySort.cpp
 * Author: mtreece
 * Date: 02/17/2010
 * Purpose:
 *  Serve as a general integer-array sorting
 *  mechanism, for selecting different methods
 *  to sort a given array of integers.
 *  Generic?  Nah - but that's for refactoring
 *  later on, or perhaps a few more google
 *  searches.
 */

#include "IntArraySort.h"

void IntArraySort::sort(int array[], int size, 
                        enum SortType type){
	switch(type){
		case INSERT_SORT:
			insertSort(array, size);
			break;
	}
}

void IntArraySort::insertSort(int array[], int size){
/*
  src: http://www.concentric.net/~ttwang/sort/insert.c
 */
  uint32 the_len = (uint32) size;
  int *This = array;
  CMPFUN fun_ptr = cmpfun;

  uint32 indx;
  int cur_val;
  int prev_val;

  if (the_len <= 1)
    return;

  prev_val = This[0];

  for (indx = 1; indx < the_len; ++indx)
  {
    cur_val = This[indx];
    if ((*fun_ptr)(prev_val, cur_val) > 0)
    {
      /* out of order: array[indx-1] > array[indx] */
      uint32 indx2;
      This[indx] = prev_val; /* move up the larger item first */

      /* find the insertion point for the smaller item */
      for (indx2 = indx - 1; indx2 > 0;)
      {
        int temp_val = This[indx2 - 1];
        if ((*fun_ptr)(temp_val, cur_val) > 0)
        {
          This[indx2--] = temp_val;
          /* still out of order, move up 1 slot to make room */
        }
        else
          break;
      }
      This[indx2] = cur_val; /* insert the smaller item right here */
    }
    else
    {
      /* in order, advance to next element */
      prev_val = cur_val;
    }
  }
}

int IntArraySort::cmpfun(int a, int b)
{
  if (a > b)
    return 1;
  else if (a < b)
    return -1;
  else
    return 0;
}


